Cenni di Programmazione Funzionale

Questo notebook è da intendersi come supporto alle slides usate in aule, di cui si richiamano alcuni punte. Le slides sono disponibili sul sito del corso.

1. High Order Functions

ESERCIZIO: Si consideri un polinomio di ordine $n$:

$$p(x) = a_0 x^0 + a_1 x^1 + ... + a_n x^n = \sum_{i=0,..,n} a_i x^i$$

Scrivere una funzione che data la lista dei coefficienti del polinomio $[a_0, a_1, ..., a_n]$ restituisca due funzioni che, dato un punto $x$, la prima funzione calcoli il valore del polinomio $p(x)$, la seconda funzione calcoli la derivata prima del polinomio:

$$p'(x) = q(x) = a_1 x^0 + 2 a_2 x^1 + ... + n a_n x^{n-1} = \sum_{i=1,..,n} a_i x^{i-1}$$



In [ ]:

    
def MakePolyAndDerivate(As):
    def Poly(x):
        return sum(a*x**n for n,a in enumerate(As))
    def PolyDerivate(x):
        return sum((n+1)*a*x**n for n,a in enumerate(As[1:]))
    return Poly, PolyDerivate

p,q = MakePolyAndDerivate([1, 0, 24])
print(p(0), q(0))
print(p(1), q(1))

2. Funzioni ricorsive

ESERCIZIO: Si scrivano le seguenti funzioni usando delle definizioni ricorsive.

Fattoriale(n)
Fibonacci(n)
IsPalindrome(stringa)



In [ ]:

    
# Fattoriale
def Fattoriale(n):
    if n == 0:
        return 1
    else:
        return n*Fattoriale(n-1)
    
print(Fattoriale(4))



In [ ]:

    
# Fibonacci
def Fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return Fib(n-1) + Fib(n-2) 
    
print(Fib(6))



In [ ]:

    
# Test if a list (e.g. string) is a palindrome
def IsPalindrome(Ls):
    if len(Ls) <= 1:
        return True
    else:
        return (Ls[0] == Ls[-1]) and IsPalindrome(Ls[1:-1])
    
print(IsPalindrome("abcdedcba"))
print(IsPalindrome("abcdeecba"))

3. List processing

Esempi da fare:

Sommatoria degli elementi di una lista: $$\mbox{sum}(Ls) = \sum_{e \in Ls} e$$
Produttoria degli elementi di una lista: $$\mbox{prod}(Ls) = \prod_{e \in Ls} e$$
Generalizzare le due funzioni precedenti in una singola funzione Fold: $$\mbox{fold}(f,v_0,[v_1,v_2,v_3,...,v_n]) = f(v_1, f(v_2, f(v_3, ... f(v_n,v_0))))$$



In [ ]:

    
def Sum(Ls):
    if Ls == []:
        return 0
    else:
        return Ls[0] + Sum(Ls[1:]) # Notazione postfix per l'addizione

# Meglio se si usa operator.add dalla libreria operator
# https://docs.python.org/3.6/library/operator.html
def Add(x,y):
    return x+y

def Sum2(Ls):
    if Ls == []:
        return 0
    else:
        return Add(Ls[0], Sum(Ls[1:])) # Notazione prefix per l'addizione



In [ ]:

    
def Mul(x,y):
    return x*y

def Prod(Ls):
    if Ls == []:
        return 1
    else:
        return Mul(Ls[0], Prod(Ls[1:]))



In [ ]:

    
def Fold(F, v, Ls):
    if Ls == []:
        return v
    else:
        return F(Ls[0], Fold(F, v, Ls[1:]))

def FoldSum(Ls):
    return Fold(Add, 0, Ls)

def FoldProd(Ls):
    return Fold(Mul, 1, Ls)

Espressività della funzione `fold`

Con la funzione fold appena vista, si possono scrivere diverse funzioni classiche che operano su delle liste. Si chiede di sviluppare come esercizio, le seguenti funzioni in termini di fold:

And(Ls): viene valutata a True se tutti gli elementi della lista sono True
Or(Ls): viene valutata a True se almeno uno degli elementi della lista è True
Length(Ls): determina la lughezza di una lista
Reverse(Ls): inverte il contenuto di una lista (esempio: [1,2,3,4] diventa [4,3,2,1])
FoldFactorial(n): una funzione che calcola il fattoriale di n
SumLength(Ls): restituisce una coppia di valori, data dalla somma degli elementi nella lista, e la lunghezza della stringa (esempio: SumLength([1,2,3,4]) = (10,4))
Map(F, Ls): una funzione map equivalente alla builtin di python
Filter(P, Ls): una funzione filter equivalente alla builtin di python



In [ ]:

    
# DA SCRIVERE LE 8 FUNZIONI RICHIESTE SOPRA

FoldRight e FoldLeft

La funzione fold scritta sopra, viene generalmente chiamata foldRight in quando applica la funzione data agli elementi della lista utilizzando la convenzione che la funzione data sia associativa a destra. Per esempio, la funzione FoldSum come implementa sopra, se applicata alla lista $[1,2,3,4,5]$, calcola $(1+(2+(3+(4+(5+0)))))$.

ESERCIZIO: Si scriva una funzione fold che assuma che per la regola data valga regola associativa a sinistra, ovvero che data la lista $[1,2,3,4,5]$, calcoli $(((((0+1)+2)+3)+4)+5)$.



In [ ]:

    
def FoldLeft(F, v, Ls):
    # DA COMPLETARE
    pass

ESERCIZIO: Si scriva la funzione reverse(Ls) utilizzando la FolfLeft invece della Fold (se non altrimenti specificato, per fold si intende la FolfRight).



In [ ]:

    
def ReverseFoldL(Ls):
    # DA COMPLETARE
    pass